МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ, МОЛОДІ ТА СПОРТУ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ІКТА
З В І Т
до лабораторної роботи №2
з курсу: «Алгоритмічні основи криптології»
на тему: «ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ»
Варіант № 9
Львів – 2013р.
Мета роботи - вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері; дослідити швидкодію алгоритмів множення довгих чисел.
Завдання
2.1. Домашня підготовка до роботи
1) Вивчити основні алгоритми множення та ділення довгих чисел, а також способи підвищення швидкодії виконання мультиплікативних операцій з довгими числами.
2) Скласти блок-схеми алгоритмів та програми для реалізації операцій множення (стовпчиком, швидке множення, множення з використанням перетворення Фур’є) або ділення довгих чисел. Варіанти представлення довгих чисел та способи заповнення невикористаних розрядів беруться з лабораторної роботи №1. Дані для роботи беруться за вказівкою викладача.
3) Дослідити швидкість виконання мультиплікативних операцій для розрядності довгих чисел від 200 до 500. Накреслити графіки відповідних залежностей і порівняти одержані результати.
2.2. Робота в лабораторії
1) Ввести в комп'ютер програми згідно з отриманим завданням.
2) Відлагодити програми. У випадку необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками.
3) Остаточні версії блок-схем, програм та отримані результати занести у звіт з лабораторної роботи.
4) Здати звіт з лабораторної роботи.
Блок-схеми алгоритму програми
Блок-схема алгоритму швидкого множення довгих чисел.
Список ідентифікаторів констант, змінних, функцій,
використаних у блок-схемі алгоритму і програмі,
та їх пояснення
a, b, c, d – одновимірні масиви типу integer.
s – змінна типу string, що використовується для зчитування довгих чисел з файлів;
Vvedennia_Chysla – метод який не має аргументів, забезпечує зчитування довгих чисел з файлів;
Vyvedennia_Chysla(int[] d, string st)– метод який реалізовує виведення довгого числа d, а також він виводить на екран значення змінної st;
Rivnist(int[] q1, int[] q2)- метод, який перевіряє рівність двох довгих чисел q1 s q2, даний метод повертає значення типу boolean(true або false);
Bilshe(int[] q1, int[] q2) - метод, що перевіряє чи число q1 є більшим за q2, повертає значення типу bool;
Dodavannia(int[] q1, int[] q2) - метод, що здійснює додавання двох довгих чисел q1 і q2.
Текст програми
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication3
{
class Program
{
static void Main(string[] args)
{
dovge_Chyslo t = new dovge_Chyslo();
Console.ReadLine();
}
}
class dovge_Chyslo
{
string s;
bool flag;
int[] a, b, c, d;
int i, j, n, g, osn, k, temp, f;
public dovge_Chyslo()
{
flag = true;
k = 4;
osn = 10000;
Zchytuvannia_a_b();
Shvydke_mn(a, b);
Vyvedennia_Chysla(d, "a*b: ");
}
void Vvedennia_Chysla()
{
FileStream stream = new FileStream(s + ".txt", FileMode.Open);
StreamReader reader = new StreamReader(stream);
s = reader.ReadToEnd();
stream.Close();
n = s.Length / k;
g = s.Length % k;
if (g != 0) n++;
c = new int[n + 1];
c[0] = n;
s.ToCharArray();
for (i = s.Length - 1; i >= g; i -= k)
{
for (j = 0, temp = 0; j < k; j++)
temp += (Convert.ToInt32(s[i - j]) - 48) * Convert.ToInt32(Math.Pow(10, j));
c[n] = temp;
n--;
}
if (g != 0)
{
for (j = 0, temp = 0; j < g; j++)
...
